package std::collection;

import std::Object;

public class HashMap : Map
{
	friend class HashMapIterator;
	friend class HashMapValueIterator;

	m_bucket->ArrayList[];
	m_size->int;
	
	public HashMap()
	{
		m_bucket=new ArrayList[32];
		m_size=0;
		i->int=0;
		while(i<m_bucket.length){
			m_bucket[i++]=new ArrayList();
		}
	}
	public HashMap(size->int)
	{
		size=size<=32?32:(1024<size?1024:size);
		m_bucket=new ArrayList[size];
		m_size=0;
		i->int=0;
		while(i<m_bucket.length){
			m_bucket[i++]=new ArrayList();
		}
	}
	public put(k->Object, v->Object)
	{
		if(k==null)return;
		buckNum->const int=m_bucket.length;
		hashcode->int=k.hashcode();
		index->int=(hashcode%buckNum+buckNum)%buckNum;
		vec->ArrayList=m_bucket[index];
		i->int=0;
		size->int=vec.size();
		while(i<size){
			pair->HashMapNode=vec.get(i);
			if(pair.key.hashcode()==hashcode){
				pair.value=v;
				return;
			}
			++i;
		}
		vec.add(new HashMapNode(k, v));
		++m_size;
	}
	public get(k->Object)->Object
	{
		if(k==null)return null;
		buckNum->const int=m_bucket.length;
		hashcode->int=k.hashcode();
		index->int=(hashcode%buckNum+buckNum)%buckNum;
		vec->ArrayList=m_bucket[index];
		i->int=0;
		size->int=vec.size();
		while(i<size){
			pair->HashMapNode=vec.get(i);
			if(pair.key.hashcode()==hashcode){
				return pair.value;
			}
			++i;
		}
		return null;
	}
	public remove(k->Object)
	{
		if(k==null)return;
		buckNum->const int=m_bucket.length;
		hashcode->int=k.hashcode();
		index->int=(hashcode%buckNum+buckNum)%buckNum;
		vec->ArrayList=m_bucket[index];
		i->int=0;
		size->int=vec.size();
		while(i<size){
			pair->HashMapNode=vec.get(i);
			if(pair.key.hashcode()==hashcode){
				vec.remove(i);
				--m_size;
				return;
			}
			++i;
		}
	}
	public exist(k->Object)->boolean
	{
		if(k==null)return false;
		buckNum->const int=m_bucket.length;
		hashcode->int=k.hashcode();
		index->int=(hashcode%buckNum+buckNum)%buckNum;
		vec->ArrayList=m_bucket[index];
		i->int=0;
		size->int=vec.size();
		while(i<size){
			pair->HashMapNode=vec.get(i);
			if(pair.key.hashcode()==hashcode){
				return true;
			}
			++i;
		}
		return false;
	}
	public empty()->boolean{return m_size==0;}
	public clear()
	{
		m_bucket=new ArrayList[32];
		m_size=0;
	}
	public size()->int{return m_size;}
	public keys()->Iterator{return new HashMapIterator(this);}
	public values()->Iterator{return new HashMapValueIterator(this);}
}

class HashMapNode : Object
{
	public key->Object;
	public value->Object;
	public HashMapNode(k->Object,v->Object){key=k;value=v;}
	public equals(e->Object)->boolean
	{
		return (e instanceof HashMapNode) && (e->(HashMapNode).key.hashcode()==key.hashcode()); 
	}
}

class HashMapIterator : Iterator
{
	protected m_map->HashMap;
	protected m_bkrow->int=0;
	protected m_bkcol->int=0;
	public HashMapIterator(map->HashMap){m_map=map;}
	public hasNext()->boolean
	{
		buckets->ArrayList[]=m_map.m_bucket;
		while(m_bkrow<buckets.length){
			bucket->ArrayList=buckets[m_bkrow];
			if(m_bkcol<bucket.size())return true;
			++m_bkrow;
			m_bkcol=0;
		}
		return false;
	}
	public next()->Object
	{
		buckets->ArrayList[]=m_map.m_bucket;
		if(m_bkrow<buckets.length){
			bucket->ArrayList=buckets[m_bkrow];
			if(m_bkcol<bucket.size()){
				return bucket.get(m_bkcol++)->(HashMapNode).key;
			}
			else return null;
		}
		else return null;
	}
}

class HashMapValueIterator : HashMapIterator
{
	public HashMapValueIterator(map->HashMap){super(map);}
	public next()->Object
	{
		buckets->ArrayList[]=m_map.m_bucket;
		if(m_bkrow<buckets.length){
			bucket->ArrayList=buckets[m_bkrow];
			if(m_bkcol<bucket.size()){
				return bucket.get(m_bkcol++)->(HashMapNode).value;
			}
			else return null;
		}
		else return null;
	}
}
